﻿#define _CRT_SECURE_NO_WARNINGS 1
// 原题连接：https://www.nowcoder.com/practice/4b2f5d4c00f44a92845bdad633965c04?tpId=230&tqId=40431&ru=/exam/oj

/*
题目描述：
给定一个正整数n，请找出最少个数的完全平方数，使得这些完全平方数的和等于n。
完全平方指用一个整数乘以自己例如1*1，2*2，3*3等，依此类推。若一个数能表示成某个整数的平方的形式，则称这个数为完全平方数。例如:1，4，9，和16都是完全平方数，但是2，3，5，8，11等等不是

数据范围:
1
≤
n
≤
1
0
4
​
1≤n≤10
4
 ​
输入描述：
仅一行，输入一个正整数 n
输出描述：
按题目要求输出完全平方数之和为n的最少个数
示例1
输入：
5
复制
输出：
2
复制
说明：
1+4=5
示例2
输入：
8
复制
输出：
2
复制
说明：
4+4=8
示例3
输入：
9
复制
输出：
1
复制
说明：
3
2
=
9

3
2
 =9
*/


#include <iostream>
#include <cstring>
using namespace std;
const int N = 110;
const int M = 10010;
int nums[N];
int n = 0;
int num = 0;
int dp[N][M];
const int INF = 0x3f3f3f3f;

int main() {
    scanf("%d", &num);
    for (int i = 1; i * i <= num; i++) {
        nums[++n] = i * i;
    }
    memset(dp, INF, sizeof dp);
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 0;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= num; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j - nums[i] >= 0) {
                dp[i][j] = min(dp[i][j], dp[i][j - nums[i]] + 1);
            }
        }
    }
    printf("%d\n", dp[n][num]);
    return 0;
}